package sort;

import java.util.Random;

public class 排序数组_912 {


    public static void main(String[] args) {
        // sortArray_merge(new int[]{5,2,3,1});
        // sortArray_fast(new int[]{5, 1, 1, 2, 0, 0});
        //sortArray_heap(new int[]{5,2,3,1});
        sortArray_heap(new int[]{-2,3,-5});

    }

    // 冒泡排序  时间复杂度 O(n^2)
    public int[] sortArray_bubble(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            // 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，
            // 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组
            boolean sorted = true;
            for (int j = 1; j <= i; j++) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                    sorted = false;
                }
            }
            if (sorted) break;
        }
        return nums;
    }

    // 选择排序 一样很慢  O(n^2)
    public int[] sortArray_select(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            int maxIdx = i;
            for (int j = 0; j <= i; j++) {
                if (nums[maxIdx] < nums[j]) {
                    maxIdx = j;
                }
            }
            swap(nums, i, maxIdx);
        }
        return nums;
    }

    // 插入排序
    public int[] sortArray_insert(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int j = i;
            int tmp = nums[i];
            // 找到目标位置 后面的右移一位
            while (j > 0 && tmp < nums[j - 1]) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = tmp;
        }
        return nums;
    }

    // 归并排序
    public static int[] sortArray_merge(int[] nums) {
        int[] tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, tmp);
        return nums;
    }

    public static void mergeSort(int[] nums, int l, int r, int[] tmp) {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        int rL = mid + 1;
        int start = l;
        int tmpL = l;
        mergeSort(nums, l, mid, tmp); // 一直往下下探到只有一个元素 层层返回合并
        mergeSort(nums, rL, r, tmp);
        // 双指针合并
        while (l <= mid && rL <= r) {
            if (nums[l] < nums[rL]) {
                tmp[start++] = nums[l++];
            } else {
                tmp[start++] = nums[rL++];
            }
        }
        while (l <= mid) {
            tmp[start++] = nums[l++];
        }
        while (rL <= r) {
            tmp[start++] = nums[rL++];
        }
        for (int i = tmpL; i <= r; i++) {
            nums[i] = tmp[i];
        }
    }


    // 快排   随机找一个数字  大于放右边小于放左边   分治往下
    public static int[] sortArray_fast(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    // 注意这种递归分治的思想  终止条件 l>=r
    public static void quickSort(int[] nums, int l, int r) {
        if (l < r) {
            int pivotIdx = partion(nums, l, r);
            quickSort(nums, l, pivotIdx - 1); // 注意  pivotIdx - 1
            quickSort(nums, pivotIdx + 1, r);// 注意  pivotIdx + 1
        }
    }

    public static int partion(int[] nums, int l, int r) {
        // 每一轮
        // 右边往左边交换一位
        // 左边往右边交换一位
        // 直到 low == high  这时的位置就是pivot(中心点、核心) 的位置
        int pivot = nums[l];
        while (l < r) {
            // 注意  == pivot 的不移动  减少无用移动 左右两个等于的反复搬动
            // 无限死循环
            // 如 0，1，1，2，0
            // while(l < r && nums[r] > pivot){  这种是有问题的  pivot = 0 不大于nums[r] = 0
            // 而是  nums[0] = nums[4]  后面while有在回过来反转
            while (l < r && nums[r] >= pivot) {
                r--;
            }
            if (l < r) nums[l] = nums[r]; // 这时候r位置空出来了
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            if (l < r) nums[r] = nums[l]; // 这时候l又空出来了
        }
        nums[l] = pivot;
        return l;  // 这时候大于nums[l] 的在右边 小于的在左边 l是中点
    }


    static class 排序数组_912_快排另一种写法 {


    // quicksort  
    public static int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int l, int r) {
        if(l < r) {
            int pivot = partion(nums, l, r);
            quickSort(nums, l, pivot - 1);
            quickSort(nums, pivot + 1, r);
        }
    }
    // 双指针都从左边开始   pivot替换到r位置
    private static int partion(int[] nums, int l, int r) {
        int pivotIdx = (int)(Math.random() * (r - l)) + l; // 随机中点
        swap(nums, pivotIdx, r); // 基准替换到r处 存在r能够在 nums[r] <= pivotNum成立 也能够替换 减少代码量
        int pivotNum = nums[r];
        int i = l - 1;
        for (int j = l; j <= r; j ++) {
            if(nums[j] <= pivotNum) {
                swap(nums, ++i, j);  // i 未知小于pivotNum的
            }
        }
        return i;
    }

    private static void swap(int[]nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    }
    /**
     * 堆排序
     */
    public static int[] sortArray_heap(int[] nums) {
        buildHeap(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            swap(nums, 0, i);
            // 交换堆顶和堆尾元素 重新从顶向下调整堆  把最大的调整到头
            heapify(nums, 0, i - 1); // 还有两个数即i= 1的时候  大的在 0 小的在1  到 还有1个数的时候  交换了 不用再交换
        }
        return nums;
    }

    public static void buildHeap(int[] nums) {
        // 初始建堆  注意
        // 1. 最后一个非叶子节点的下标  *** n/2 - 1 ***
        // 2. i>=0  否则0处没法和子节点交换
        for (int i = (nums.length>> 1)  - 1; i >= 0; i--) {
            heapify(nums, i, nums.length -1 );
        }
    }

    // 升序排列 需要建立大根堆  而后倒序和尾部元素交换重排序
    // length 用来限制调整到什么位置为止  防止堆排序过程重排了
    public static void heapify(int[] nums, int i, int length) {
        int right = (i + 1) << 1;
        int left = right - 1;
        int max = i;

        // length 应该是可达边界 因此这里是 <=  而不是 <
        if (right <= length && nums[right] > nums[max]) {
            max = right;
        }

        if (left <= length && nums[left] > nums[max]) {
            max = left;
        }

        if (max == i) return;
        swap(nums, max, i);
        heapify(nums, max, length);
    }


    public static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}
